package codetop.kuaishou.T312;

/**
 * @Author: 18362
 * @Create: 2022-09-16 2:14:34 星期五
 */
class Solution {

    private int[] nums;

    public int maxCoins(int[] nums) {
        int n = nums.length;
        this.nums = nums;
        int[][] dp = new int[n+2][n+2];
        for (int i=0; i<n; ++i)
            dp[i][i+2] = value(i) * value(i+1) * value(i+2);
        for (int step = 3; step < n+2; ++step) {
            for (int i=0; i+step<n+2; ++i) {
                int j = i+step;
                for (int k=i+1; k<j; ++k)
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + value(i) * value(k) * value(j) + dp[k][j]);
            }
        }
        return dp[0][n+1];
    }

    private int value(int i) {
        if (i == 0 || i == nums.length + 1)
            return 1;
        return nums[i-1];
    }
}